package com.hjx.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 *
 */
class LeetCode_46 {

    /**
     * 存放 符合条件的排列结果
     */
    private List<List<Integer>>  res = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        //当前选择路径的容器
        List<Integer> track = new ArrayList<>();
        backTrack(nums, track);
        return res;
    }

    /**
     * 回溯法求全排列
     * @param nums
     * @param track
     */
    public void backTrack(int[] nums, List<Integer> track) {
        // 当遍历全排列树时 一条路径走到头后 则求得一个全排列,将全排列放到结果集中，由于需要做选择或者撤销选择 所以要拷贝完整的track 存放到结果集
        if (nums.length == track.size()) {
            res.add(new ArrayList<>(track));
            //求的一个解 结束
            return;
        }
        // 未遍历到最底层 选择 继续遍历数组  for循环时间复杂度O(n)
        for (int i = 0; i < nums.length; i++) {
            //先排除非法选择，已经存在于链表中的为选择过的数字, 此处比较需要遍历 时间复杂度O(n)
            if (track.contains(nums[i])) {
                continue;
            }
            //做选择
            track.add(nums[i]);
            //递归遍历 遍历到一个叶子节点的复杂度为O(n!)
            backTrack(nums, track);
            //到达底部后撤销选择,移除最后一个元素,下次循环选择数组下一个元素
            track.remove((Integer)(nums[i]));
//            track.remove(track.size()-1);
        }


    }

}
